//编写一个函数来查找字符串数组中的最长公共前缀。
//
// 如果不存在公共前缀，返回空字符串 ""。
//
//
//
// 示例 1：
//
//
//输入：strs = ["flower","flow","flight"]
//输出："fl"
//
//
// 示例 2：
//
//
//输入：strs = ["dog","racecar","car"]
//输出：""
//解释：输入不存在公共前缀。
//
//
//
// 提示：
//
//
// 1 <= strs.length <= 200
// 0 <= strs[i].length <= 200
// strs[i] 如果非空，则仅由小写英文字母组成
//
//
// Related Topics 字典树 数组 字符串 👍 3402 👎 0

import enums.Way;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;

/**
 * 最长公共前缀
 */
public class LongestCommonPrefix {
    public static String longestCommonPrefix(String[] strs, Way way) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        switch (way){
            case WAY1:
                return way1(strs);
            case WAY2:
                return way2(strs);
            case WAY3:
                return way3(strs);
            case WAY4:
                return way4(strs);
            case WAY5:
                return way5(strs);
            default:
                throw new IllegalArgumentException("Way is not exist.");
        }
    }

    /**
     * 暴力法
     * 时间复杂度：O(n*m²)，n为数组长度，m为第一个字符串长度
     * 空间复杂度：O(m²)
     */
    private static String way1(String[] strs){
        String str = strs[0];
        HashMap<String,Integer> map = new LinkedHashMap<>();
        for (int i = str.length() - 1; i >= 0; i--){
            map.put(str.substring(0,i+1),i);
        }
        for (int i = 0; i < strs.length; i++){
            Iterator<String> iterator = map.keySet().iterator();
            while (iterator.hasNext()){
                String key = iterator.next();
                if (!strs[i].startsWith(key)){
                    iterator.remove();
                }
            }
        }
        return map.isEmpty() ? "" : map.keySet().iterator().next();
    }

    /**
     * 纵向扫描
     * 时间复杂度：O(n*m)，n为数组长度，m为第一个字符串长度
     * 空间复杂度：O(1)
     */
    private static String way2(String[] strs) {
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int length = Math.min(prefix.length(), strs[i].length());
            int index = 0;
            while (index < length && prefix.charAt(index) == strs[i].charAt(index)) {
                index++;
            }
            prefix = prefix.substring(0, index);
            if (prefix.isEmpty()) {
                break;
            }
        }
        return prefix;
    }

    /**
     * 纵向扫描
     * 时间复杂度：O(n*m)，n为数组长度，m为第一个字符串长度
     * 空间复杂度：O(1)
     */
    private static String way3(String[] strs) {
        String prefix = strs[0];
        for (int i = 0; i < prefix.length(); i++){
            char c = prefix.charAt(i);
            for (int j = 1; j < strs.length; j++){
                if (i == strs[j].length() || strs[j].charAt(i) != c){
                    return prefix.substring(0,i);
                }
            }
        }
        return prefix;
    }

    /**
     * 分治法
     * 时间复杂度：O(n*m)，n为数组长度
     * 空间复杂度：O(log n)
     */
    private static String way4(String[] strs) {
        return way4(strs, 0, strs.length - 1);
    }

    private static String way4(String[] strs, int left , int right){
        if (left == right){
            return strs[left];
        }else{
            int mid = (right - left) / 2 + left;
            String lcpLeft = way4(strs, left, mid);
            String lcpRight = way4(strs, mid + 1, right);
            int length = Math.min(lcpLeft.length(), lcpRight.length());
            for (int i = 0; i < length; i++){
                if (lcpLeft.charAt(i) != lcpRight.charAt(i)){
                    return lcpLeft.substring(0, i);
                }
            }
            return lcpLeft.substring(0, length);
        }
    }

    /**
     * 二分查找
     * 时间复杂度O(n*m*log m)
     * 空间复杂度O(1)
     */
    private static String way5(String[] strs) {
        int minLength = strs[0].length();
        for (String s : strs){
            minLength = Math.min(minLength, s.length());
        }
        int left = 0,right = minLength;
        while (left < right){
            int mid = (right - left + 1) / 2 + left;
            if (isCommonPrefix(strs, mid)){
                left = mid;
            }else{
                right = mid - 1;
            }
        }
        return strs[0].substring(0, left);
    }

    private static boolean isCommonPrefix(String[] strs, int length){
        String str = strs[0].substring(0, length);
        for (int i = 1; i < strs.length; i++){
            if (!strs[i].startsWith(str)){
                return false;
            }
        }
        return true;
    }
}
